Адміністрація вирішила продати даний сайт. За детальною інформацією звертайтесь за адресою: rozrahu@gmail.com

Лабораторна №2

Інформація про навчальний заклад

ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра СКС

Інформація про роботу

Рік:
2013
Тип роботи:
Лабораторна робота
Предмет:
Дискретна математика

Частина тексту файла

Міністерство освіти і науки України Національний університет „Львівська політехніка” Кафедра СКС Звіт з лабораторної роботи № 2 з дисципліни: “Дискретна матетематика” на тему: “ Задача про кістякове дерево екстремальної (мінімальної або максимальної) ваги ” Мета: навчитися створювати програму яка обчислює задачу про кістякове дерево екстремальної (мінімальної або максимальної) ваги Теоретичні відомості При знаходженні кістякового дерева графа підхід із відкиданням ребер не є ефективним через те, що складно перевіряти наявність циклів в утворюваному графі. Ефективним є підхід із конструюванням (утворенням) кістяка. У цьому разі просто перевіряти наявність циклів в графі, що виникає. Вказаний підхід реалізує алгоритм Пріма (так званий алгоритм найближчого сусіда). Крок 1. Присвоєння початкових значень. S'={Xα}, Xα - довільна вершина графа (скажімо, перша за номером). S''= S\S', V' = Ø Крок 2. Оновлення даних. Знаходимо таке ребро (Xi, Xj), що Xi ϵ S', Xj ϵ S'' та W(Xi, Xj)= min{ W(Xα, Xβ)| Xα ϵ S', Xβ ϵ S''} Покладаємо S' = S' U { Xi }, S'' = S\S', V' = V'U{(Xi, Xj)} Крок 3. Перевірка на завершення. Якщо S' = S, то G' = (S', V') - шуканий граф. В іншому випадку переходимо на Крок 2. Далі наведено приклад виконання алгоритму Пріма. Граф задано списком ребер з вказанням їх ваг. (1,4|1), (4,1|1), (1,5|3), (5,1|3), (2,3|3), (3,2|3), (2,4|5), (4,2|5), (2,5|4), (5,2|4), (3,5|4), (5,3|4), (4,5|2), (5,4|2). Відповідний цьому списку граф  Спершу впорядковуємо ребра за зростанням їх ваг. Для цього слід використати якийсь алгоритм сортування. (1,4|1), (4,1|1), (4,5|2), (5,4|2), (1,5|3), (5,1|3), (2,3|3), (3,2|3), (2,5|4), (5,2|4), (3,5|4), (5,3|4), (2,4|5), (4,2|5). Тепер власне виконуємо алгоритм Пріма (додаючи для кожного кроку 2 ребро мінімальної ваги). S = {1,2,3,4,5} Крок 1. S' = {1} S'' = {2,3,4,5} V' = Ø Крок 2 . V' = V'U{(1,4|1)}={(1,4|1)} S' = {1,4} S'' = {2,3,5} Крок 3. S'≠S Крок 2. V' = V'U{4,5|2} = {(1,4|1), (4,5|2)} Крок 3. S'≠S Крок 2. V' = V'U {(5,2|4)} = {(1,4|1), (4,5|2), (5,2|4)} S' = {1,2,4,5} S'' = {3} Крок 3. S'≠S Крок 2. V' = V'U {(2,3|3)} = {(1,4|1), (4,5|2), (5,2|4), (2,3|3)} S' = {1,2,3,4,5} S'' = Ø Крок 3. S'=S Таким чином, отримали таке кістякове дерево мінімальної ваги для початкового графа.  Вага отриманого кістякового дерева дорівнює 10. Код програми мовою Delphi: unit Pasik; interface uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, Buttons, Grids; type TForm1 = class(TForm) StringGrid1: TStringGrid; Label1: TLabel; BitBtn2: TBitBtn; Label2: TLabel; procedure FormCreate(Sender: TObject); procedure FormPaint(Sender: TObject); procedure DrawLine(a1,a2,c: integer); procedure StringGrid1SetEditText(Sender: TObject; ACol, ARow: Integer; const Value: String); procedure BitBtn2Click(Sender: TObject); procedure DrawGraph; private { Private declarations } public { Public declarations } end; TMyPoint=record x:integer; y:integer; name:string end; var Form1: TForm1; MyPoint:array[1..5] of TMyPoint; koef:integer; implementation {$R *.dfm} procedure TForm1.DrawGraph; var x,kx,ky,a,b:integer; begin Form1.Refresh; for x:=1 to 5 do begin kx:=MyPoint[x].x+koef; ky:=MyPoint[x].y+koef; Form1.Canvas.Ellipse(kx,ky,kx+10,ky+10); Form1.Canvas.TextOut(kx,ky-15,MyPoint[x].name); end; for a:=2 to 5 do for b:=1 to a-1 do if ((StringGrid1.Cells[b,a]<>'') and (StrtoInt(StringGrid1.Cells[b,a])>0)) then DrawLine (a,b,1); end; procedure TForm1.DrawLine(a1,a2,c: integer); var x1,y1,x2,y2:integer; begin if c=1 then Form1.Canvas.Pen.Color:=clBlack; if c=2 t...
Антиботан аватар за замовчуванням

15.10.2013 11:10

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, увійдіть або зареєструйтесь.

Завантаження файлу

Якщо Ви маєте на своєму комп'ютері файли, пов'язані з навчанням( розрахункові, лабораторні, практичні, контрольні роботи та інше...), і Вам не шкода ними поділитись - то скористайтесь формою для завантаження файлу, попередньо заархівувавши все в архів .rar або .zip розміром до 100мб, і до нього невдовзі отримають доступ студенти всієї України! Ви отримаєте грошову винагороду в кінці місяця, якщо станете одним з трьох переможців!
Стань активним учасником руху antibotan!
Поділись актуальною інформацією,
і отримай привілеї у користуванні архівом! Детальніше

Оголошення від адміністратора

Антиботан аватар за замовчуванням

пропонує роботу

Admin

26.02.2019 12:38

Привіт усім учасникам нашого порталу! Хороші новини - з‘явилась можливість кожному заробити на своїх знаннях та вміннях. Тепер Ви можете продавати свої роботи на сайті заробляючи кошти, рейтинг і довіру користувачів. Потрібно завантажити роботу, вказати ціну і додати один інформативний скріншот з деякими частинами виконаних завдань. Навіть одна якісна і всім необхідна робота може продатися сотні разів. «Головою заробляти» продуктивніше ніж руками! :-)

Новини